#include "doublelist.h"

Head *createlist()
{
    //开辟管理者节点空间，并且初始化
    Head *ph = (Head *)malloc(sizeof(Head));
    ph->first = NULL;
    ph->last = NULL;
    ph->nodenum = 0;
    return ph;
}

void inserTolist(Datatype num,Head *h)
{
    if(h == NULL)
    {
        printf("链表不存在\n");
        return ;
    }
    //为num分配一个节点空间
    PNode pnew = (PNode)malloc(sizeof(Node));
    pnew->data = num;
    pnew->next = NULL;
    pnew->prev = NULL;
        if(h->first == NULL)//从无到有
        {
            h->first = pnew;
            h->last = pnew;
        }
        else
        {
            //头插法
            //pnew->next = h->first;
            //h->first = pnew;
            //h->first = prev;
            //尾插法
            h->last->next = pnew;
            pnew->prev = h->last;
            h->last = pnew;
        }
        h->nodenum++;
}

void inser_high_Tolist(Datatype num,Head *h)
{
    if(h == NULL)
    {
        printf("链表不存在\n");
        return ;
    }
    //为num分配一个节点空间
    PNode pnew = (PNode)malloc(sizeof(Node));
    pnew->data = num;
    pnew->next = NULL;
    pnew->prev = NULL;
    if(h->first == NULL)//从无到有
    {
        h->first = pnew;
        h->last = pnew;
    }
    else
    {
        if(pnew->data <= h->first->data)//新节点数据最小
        {
                //头插法
            pnew->next = h->first;
            h->first->prev = pnew;
            h->first = pnew;
        }
        else if(pnew->data >= h->last->data)//新节点数据最大
        {
            //尾插法
            h->last->next = pnew;
            pnew->prev = h->last;
            h->last = pnew;
        }
        else//插在中间
        {
            //建立一个遍历p
            Node *p = h->first;
            while(1)
            {
                //当p的data大于pnew的data,跳出循环
                if(p->data >=pnew->data)
                {
                    break;
                }
                p = p->next;
            }
            p->prev->next = pnew;
            pnew->prev = p->prev;
            p->prev = pnew;
            pnew->next = p;
        }
            
    }
    h->nodenum++;
}

void printflist(Head *h)
{
    if(h == NULL)
    {
        printf("链表不存在!\n");
        return ;
    }
    printf("Node num:%d\n",h->nodenum);
    printf("正链表输出:");
    Node *p = h->first;
    while(p)
    {
        printf("%d  ",p->data);
        p = p->next;
    }
    printf("\n");
    printf("反链表输出:");
    Node *p1 = h->last;
    while(p1)
    {
        printf("%d  ",p1->data);
        p1 = p1->prev;
    }
    printf("\n");
}

/*
void printflist(Head *h)
{
    
    PNode p = h->first;
    while(p)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
    while(p)
    {
        printf("%d ",p->data);
        p = p->prev;
    }
    printf("\n");
}
*/

void clearlist(Head *head)
{
   if(head == NULL || head->first == NULL)
   {
        return ;
   }
   //一个一个的释放节点
   while(head->first)
   {
    Node *p = head->first;
    head->first = p->next;
    p->next = NULL;
    p->prev = NULL;
    free(p);
    head->nodenum--;
    //printf("\n ok");
   }
   head->last = NULL;
}

void deletelist(Head *h)
{
    //清空整个链表
    clearlist(h);
    //释放头结点
    free(h);
}

//删除最小值
void deleteMin(Head *h)
{
    if(h == NULL)
    {
        return ;
    }
    //建立一个遍历节点pnew
    Node *pnew = h->first;
    Node *p = pnew->next;
    //循环
    while(p)
    {
        if(pnew->data >= p->data)//如果pnew大于它的下一个
        {
            pnew = p;//pnew直接跳到p
        }
         p = p->next;//p继续走 
    }
    //分情况删除 
    //如果最小的是第一个
    if(pnew == h->first)
    {
        h->first = h->first->next;
        pnew->next = NULL;
        if(h->first != NULL)   //链表中有很多节点
        {
            h->first->prev = NULL;
        }else                   //链表中仅有一个节点
        {
            h->last = NULL;
        }
    }
    else if(pnew == h->last)//要删除的节点是最后一个
    {
        h->last = pnew->prev;
        h->last->next = NULL;
        pnew->prev = NULL;
    }
    else
    {
        pnew->prev->next = pnew->next;
        pnew->next->prev = pnew->prev;
        pnew->next = NULL;
        pnew->prev = NULL; 
    }
    free(pnew);
    h->nodenum--;
        
}


/*删除指定的链表中的值X*/
void delete_x(Head *h,Datatype x)
{
    Node *p = NULL;
    
}